package dp.一维数组;


import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/house-robber-iii/?favorite=2cktkvj
 *
 * 题解：https://mp.weixin.qq.com/s/tcM2I6DGMA8oF0cSyKG59g
 */
public class _337_打家劫舍III {

    public int rob(TreeNode root) {
        return dp(root);
    }

    Map<TreeNode, Integer> meno = new HashMap<>();

    private int dp(TreeNode root) {
        if (root == null) return 0;

        if (meno.containsKey(root)) {
            return meno.get(root);
        }

        int result1 = root.val + dp(root.left != null ? root.left.left : null) + dp(root.left != null ? root.left.right : null)
                + dp(root.right != null ? root.right.left : null) + dp(root.right != null ? root.right.right : null);

        int result2 = dp(root.left) + dp(root.right);

        int result = Math.max(result1, result2);

        meno.put(root, result);

        return result;
    }


}
